Sparsely populated data sets are utilized in numerous technical fields. The present invention was developed for efficiently encoding image data that has been transformed by successive applications of wavelet transforms, but is equally applicable to other types of sparsely populated data sets. Image data that has been transformed by successive applications of wavelet transforms tends to have large portions occupied by zero and near-zero values, especially if the data is subjected to a data quantization step prior to encoding.
The primary goals of the present invention are to provide an encoding methodology that (A) efficiently locates subarrays that are entirely occupied by zero and near-zero data and encoding such subarrays with as few data bits as possible, (B) determines the maximum number of data bits required to encode subarrays that include at least some non-zero data, and (C) encodes non-zero data with the minimum number of data bits required to losslessly store such data.
Another goal of the present invention is to provide a mechanism for selectively or controllably reducing the size of a compressed data file while losing as little information as possible.
Other goals of the present invention are to provide an encoding methodology that is computationally very efficient, and one that is suitable for implementation in part or completely in hardware (i.e., electronic circuitry).
Yet another goal is to provide an encoding and decoding methodology that facilitates "on-the-fly" decoding and partial image reconstruction while an array of encoded, compressed data is still being received, enabling users to view a partially reconstructed image before the receiving system has finished receiving the encoded, compressed data.